// Created by WXX on 2021/11/30 14:33
#include "MyTree.h"

/**
 * 执行用时：20 ms, 在所有 C++ 提交中击败了61.84%的用户
 * 内存消耗：20.4 MB, 在所有 C++ 提交中击败了24.73%的用户
 */
#define x first
#define y second

typedef pair<int, int> PII;

class Solution {
public:
    vector<PII> nodes;
    int k = 0; // dfs中遍历到nodes[k]

    TreeNode* dfs(int d) {  // d: 遍历的深度

        auto root = new TreeNode(nodes[k].y);

        k++;
        if (k < nodes.size() && nodes[k].x > d)
            root->left = dfs(d + 1);
        if (k < nodes.size() && nodes[k].x > d)
            root->right = dfs(d + 1);

        return root;
    }

    TreeNode* recoverFromPreorder(string str) {

        for (int i = 0; i < str.size(); ) {
            int dep = 0;
            while (str[i] == '-') dep++, i++;
            int val = 0;
            while (i < str.size() && str[i] != '-')
                val = val * 10 + str[i++] - '0';
            nodes.push_back({dep, val});
        }

        return dfs(0);
    }
};

int main() {


    return 0;
}
